
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int start = 0;
        // 用一个哈希表存储T中每个字符出现的次数，window记录窗口中有效的字符和数量
        Map<Character, Integer> window = new HashMap<>();
        // need记录需要的字符和数量
        Map<Character, Integer> need = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        // 存储滑动窗口的长度
        int valid = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            // 每次移动right指针，将窗口内的字符出现的次数加一
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 如果字符c在T中出现的次数不为0，且window中出现的次数不大于T中出现的次数，则valid加一
            if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
                valid++;
            }
            // 当valid等于T的长度时，表示窗口中已经覆盖了T中所有字符，此时开始移动left指针
            while (valid == need.size()) {
                // 更新最小子串长度
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                // 移除起始位置字符，并将valid减一
                char d = s.charAt(left);
                window.put(d, window.get(d) - 1);
                if (need.containsKey(d) && window.get(d).intValue() < need.get(d).intValue()) {
                    valid--;
                }
                // 移动left指针
                left++;
            }
            // 移动right指针
            right++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

}
//leetcode submit region end(Prohibit modification and deletion)
